import java.util.Arrays;

public class Solution {
    private int[] prices;
    private int[][] memo;

    public int maxProfit(int[] prices) {
        this.prices = prices;
        int n = prices.length;
        memo = new int[n][2];
        for (int[] row : memo) {
            Arrays.fill(row, -1); // -1 表示还没有计算过
        }
        return dfs(n - 1, 0);
    }

    private int dfs(int i, int hold) {
        if (i < 0) {
            return hold == 1 ? Integer.MIN_VALUE : 0;
        }
        if (memo[i][hold] != -1) { // 之前计算过
            return memo[i][hold];
        }
        if (hold == 1) {
            return memo[i][hold] = Math.max(dfs(i - 1, 1), dfs(i - 2, 0) - prices[i]);
        }
        return memo[i][hold] = Math.max(dfs(i - 1, 0), dfs(i - 1, 1) + prices[i]);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] prices = {1,2,3,0,2};
        System.out.println("The maximum profit is: " + solution.maxProfit(prices));
    }
}